package day14_100;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName Solution
 * @Description TODO BFS
 * @Author clockTown
 * @Date 2021/5/23 20:21
 * @Version 1.0
 */
public class Solution2 {
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null){
            return true;
        }
        if (p == null || q == null) {
            return false;
        }

        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(p);
        queue2.offer(q);

        while (!queue1.isEmpty() && !queue2.isEmpty()){
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();

            if (node1.val != node2.val){
                return false;
            }

            TreeNode left1 = node1.left;
            TreeNode right1 = node1.right;
            TreeNode left2 = node2.left;
            TreeNode right2 = node2.right;

            if (left1 == null ^ left2 == null) {
                return false;
            }
            if (right1 == null ^ right2 == null) {
                return false;
            }
            if (left1 != null){
                queue1.offer(left1);
            }
            if (left2 != null){
                queue2.offer(left2);
            }
            if (right1 != null){
                queue1.offer(right1);
            }
            if (right2 != null){
                queue2.offer(right2);
            }

        }
        return queue1.isEmpty() && queue2.isEmpty();
    }
}
